package com.leetcode.practice.quesions;

import java.util.HashMap;
import java.util.Map;

import com.leetcode.practice.interfaces.IQuestion;

/**
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

	你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
	
	示例:
	
	给定 nums = [2, 7, 11, 15], target = 9
	
	因为 nums[0] + nums[1] = 2 + 7 = 9
	所以返回 [0, 1]
	
	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/two-sum

 * @author Administrator
 *
 */
public class q1_两数之和  implements IQuestion{

	int[] nums = {2, 7, 11, 15};
	int target = 9;
	
	@Override
	public void solution() {
		solution1();
	}
	
	/**
	 * 暴力破解法
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(1)
	 */
	private void solution1() {
		int[] result= new int[2];
		// TODO Auto-generated method stub
		top:
		for(int i=0;i<nums.length-1;i++) {
			for(int j=i+1;j<nums.length;j++) {
				if(nums[i]==target-nums[j]) {
					result[0]=nums[i];
					result[1]=nums[j];
					break top;
				}
			}
		}
		
		System.out.println("result->["+result[0]+","+result[1]+"]");
	}
	
	/**
	 * 哈希表破解法
	 * 
	 * 时间复杂度：O(n)
	 * 空间复杂度：O(n)
	 */
	public void solution2() {
		int[] result= new int[2];
		Map<Integer,Integer> map=new HashMap();
		for(int i=0;i<nums.length;i++) {
			map.put(i, nums[i]);
		}
		for(int i=0;i<nums.length;i++) {
			int s=target-nums[i];
			if(map.containsValue(s)) {
				result[0]=nums[i];
				result[1]=s;
				break;
			}
		}
		System.out.println("result->["+result[0]+","+result[1]+"]");
		
	}

	
	public static void main(String[] args) {
		q1_两数之和  q=new q1_两数之和();
		q.solution();
	}
	
}
